package cfsmon.logic.nfm;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import cfsmon.common.Event;

public class NfmOptimizer {

	private static Logger logger = Logger.getLogger(NfmOptimizer.class);
	
	public static INfm optimize(INfm nfm) {
		logger.info("Performing NFM optimization.");
		if (nfm != null){
			reduceToReachableSet(nfm);
			removeRedundantEventTransitions(nfm);
			/* An NFM may validly have no final state.
			 * if (!hasAtLeastOneFinalState(nfm)){ // this state must be reachable
				logger.error("The NFM has no reachable final state.");
				return null;
			}*/
		}
		return nfm;
	}
	
	private static void reduceToReachableSet(INfm nfm){
		logger.info("Reduction of the NFM to reachable states.");
		Set<NfmState> reached = new HashSet<NfmState>();
		Set<NfmState> currentState = new HashSet<NfmState>();
		Set<NfmState> nextState;

		// determine reachable set
		
		currentState.addAll(nfm.getInitialStates());
		
		while (!currentState.isEmpty()){
			
			nextState = new HashSet<NfmState>();
			
			for (NfmState s : currentState){
				
				// if default transitions can be triggered
				if (!s.getTransitions().keySet().containsAll(nfm.getEvents().values())){
					// add default transitions
					nextState.addAll(s.getDefaultTransition());
				}
				
				// add event transitions				
				for (Set<NfmState> tr : s.getTransitions().values()){
					nextState.addAll(tr);
				}
			}
			
			reached.addAll(currentState);
			nextState.removeAll(reached);
			
			currentState.clear();
			currentState = nextState;
		}
		
		// drop unreachable states
		
		Iterator<Map.Entry<String, NfmState>> it = nfm.getStates().entrySet().iterator();
		while (it.hasNext()){
			Map.Entry<String, NfmState> entry = it.next();
			if (!reached.contains(entry.getValue())){
				logger.debug("Unreachable state detected and removed: <" + entry.getKey() + ">.");
				it.remove();
			}
		}
		
		// drop unreachable final states
		
		Iterator<NfmState> finalIt = nfm.getFinalStates().iterator();
		while (finalIt.hasNext()){
			NfmState s = finalIt.next();
			if (!reached.contains(s)){
				finalIt.remove();
			}
		}
		
	}
	
	private static void removeRedundantEventTransitions(INfm nfm){
		for (NfmState s : nfm.getStates().values()){
			Iterator<Map.Entry<Event, Set<NfmState>>> it = s.getTransitions().entrySet().iterator();
			while (it.hasNext()){
				Map.Entry<Event, Set<NfmState>> entry = it.next();
				
				if (s.getDefaultTransition().containsAll(entry.getValue()) && entry.getValue().containsAll(s.getDefaultTransition())){
					logger.debug("Redundant Transition <" + s + "-[" + entry.getKey() + "]->" + entry.getValue().toString() + "> detected and removed.");
					it.remove();
				}
			}
		}
	}
	
	private static boolean hasAtLeastOneFinalState(INfm nfm){
		return !nfm.getFinalStates().isEmpty();
	}
}
